﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <string>
using namespace std;

//解码方法
//https://leetcode.cn/problems/decode-ways/submissions/
//常规解法
//class Solution {
//public:
//    int numDecodings(string s) {
//        int n = s.size();
//        vector<int> dp(n);
//
//        dp[0] = (s[0] != '0'); //第一个字符不为0一定可以解码
//        if (n == 1) return dp[0];
//
//        if (s[0] != '0' && s[1] != '0') dp[1] += 1; //如果第一个和第二个字符都不为0则第二个字符可以单独解码
//        int num = (s[0] - '0') * 10 + s[1] - '0';
//        if (num >= 10 && num <= 26) dp[1] += 1; //两个字母也可以解码
//
//        for (int i = 2; i < n; ++i)
//        {
//            if (s[i] != '0') dp[i] += dp[i - 1]; //如果当前位置可以解码，则当前位置解码次数为上一个字母的解码次数
//            int num = (s[i - 1] - '0') * 10 + s[i] - '0'; //计算上一个字母释放可以一起解码
//            if (num >= 10 && num <= 26) dp[i] += dp[i - 2]; //两个字母也可以解码则将i-1和i字母看做一个整体 此时解码次数为i-2
//            //如果单独可以解码且两个也可以解码 则是dp[i-1]+dp[i-2]的解码次数
//        }
//        return dp[n - 1];
//    }
//};
//优化代码
//class Solution {
//public:
//    int numDecodings(string s) {
//        int n = s.size();
//        vector<int> dp(n + 1);
//        dp[0] = 1;// 多开一位处理冗余代码 当s[0]和s[1]可以解码是加上的是dp[0]和dp[1]如果此时dp[0]为0则s[2]在判断时会出错
//
//        dp[1] = (s[0] != '0'); //第一个字符不为0一定可以解码
//        if (n == 1) return dp[1];
//
//        for (int i = 1; i < n; ++i)
//        {
//            if (s[i] != '0') dp[i + 1] += dp[i]; //如果当前位置可以解码，则当前位置解码次数为上一个字母的解码次数
//            int num = (s[i - 1] - '0') * 10 + s[i] - '0'; //计算上一个字母释放可以一起解码
//            if (num >= 10 && num <= 26) dp[i + 1] += dp[i - 1]; //两个字母也可以解码则将i-1和i字母看做一个整体 此时解码次数为i-2
//            //如果单独可以解码且两个也可以解码 则是dp[i-1]+dp[i-2]的解码次数
//        }
//        return dp[n];
//    }
//};

//不同路径1
//https://leetcode.cn/problems/unique-paths/submissions/
//class Solution {
//public:
//    int uniquePaths(int m, int n) {
//        vector<vector<int>> vv(m, vector<int>(n));
//        for (int i = 0; i < vv.size(); ++i)
//        {
//            for (int k = 0; k < vv[i].size(); ++k)
//            {
//                if (i == 0 || k == 0) vv[i][k] = 1;
//                else vv[i][k] = vv[i - 1][k] + vv[i][k - 1];
//            }
//        }
//        return vv[m - 1][n - 1];
//    }
//};
//多开空间省去判断
//class Solution {
//public:
//    int uniquePaths(int m, int n) {
//        vector<vector<int>> vv(m + 1, vector<int>(n + 1));
//        vv[0][1] = 1;
//        for (int i = 1; i <= m; ++i)
//            for (int k = 1; k <= n; ++k)
//                vv[i][k] = vv[i - 1][k] + vv[i][k - 1];
//
//        return vv[m][n];
//    }
//};

//不同路径2
//https://leetcode.cn/problems/unique-paths-ii/
//class Solution {
//public:
//    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
//        if (obstacleGrid[0][0] == 1) return 0;
//
//        int m = obstacleGrid.size();
//        int n = obstacleGrid[0].size();
//        vector<vector<int>> vv(m + 1, vector<int>(n + 1));
//        vv[0][1] = 1;
//        for (int i = 1; i <= m; ++i)
//        {
//            for (int k = 1; k <= n; ++k)
//            {
//                if (obstacleGrid[i - 1][k - 1] == 1) continue;
//                vv[i][k] = vv[i - 1][k] + vv[i][k - 1];
//            }
//        }
//        return vv[m][n];
//    }
//};